import numpy as np

class ConvexHull(object):

    TURN_LEFT, TURN_RIGHT, TURN_NONE = (1, -1, 0)
    
    @staticmethod
    def turn(p, q, r):
        return cmp((q[0] - p[0])*(r[1] - p[1]) - (r[0] - p[0])*(q[1] - p[1]), 0)
      
    @staticmethod
    def _keep_left(hull, r):
        while len(hull) > 1 and ConvexHull.turn(hull[-2], hull[-1], r) != ConvexHull.TURN_LEFT:
                hull.pop()
        if not len(hull) or not (hull[-1] == r).all():
            hull.append(r)
        return hull
    
    @staticmethod 
    def convex_hull(points):
        """Returns points on convex hull of an array of points in CCW order."""
        points = points[np.lexsort((points[:,1],points[:,0]))]
        l = reduce(ConvexHull._keep_left, points, [])
        u = reduce(ConvexHull._keep_left, reversed(points), [])
        return l.extend(u[i] for i in xrange(1, len(u) - 1)) or l 


if __name__ == "__main__":
    points = [(0,0),(0,20),(20,18)]
    out = ConvexHull.convex_hull(np.array(points))
    print out